"""
首先，利用快慢指针找到中间节点，无论是奇数还是偶数，将slow指针下移一位表示new_head
然后，将slow指针与后半段断开，得到前后两端链表，翻转new_head链表（后半段链表）
接下来，创建指针p1，p2分别指向前后指针的头部，p1_next,p2_next分别指向p1,p2指针的后一位
最后，拼接两端链表
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # 1 特殊情况：只有1或2个节点，直接返回
        if head.next is None or head.next.next is None:
            return head
        
        # 首先
        slow, fast = head, head

        while True:
            if fast.next and fast.next.next:
                slow = slow.next
                fast =fast.next.next
            else:
                break
        
        new_head = slow.next

        # 然后
        slow.next = None

        def reverse(head):
            if head is None or head.next is None:
                return head
            
            last = reverse(head.next)
            head.next.next = head
            head.next = None
            return last
        
        p2 = reverse(new_head)

        # 接下来
        p1 = head
        
        # 因为p2比较短，所以用p2指针遍历
        while p2:
            p1_next, p2_next = p1.next, p2.next
            
            p1.next = p2
            p2.next = p1_next

            p1, p2 = p1_next, p2_next
        
        return head